package Runde4;

public abstract class SortedTree extends StringTree {
	
	/**
	 * @precondition root.length() > 0 and root != NULL
	 * @postcondition Creates a new binary search tree with the given root node, labeled with the given name.
	 * @param root The label of the root node.
	 * @throws InvalidParamException If the preconditions are not met.
	 */
	public SortedTree(String root) throws InvalidParamException {
		super(root);
	}
	
	/**
	 * @precondition node.length() > 0 and node != NULL
	 * @postcondition Returns the path to the node labeled with the given String. If no such node exists, "Node not found" is returned.
     * @param node Label of the node to search for.
	 * @throws InvalidParamException If the preconditions are not met.
	 */
	public String search(String node) throws InvalidParamException {
		try {
			checkParam(node);
			return suche(node, root);
		} catch (InvalidParamException e) {
			throw e;
		}
	}
	
	/**
	 * @precondition node.length() > 0 and node != NULL
	 * @postcondition Adds a node with the given label to the tree, maintaining the sorting. 
	 * @param node Label of the node to add.
	 * @throws InvalidParamException If the preconditions are not met.
	 */
	public void add(String node) {
		try {
			checkParam(node);
			recAdd(node, root);
		} catch (InvalidParamException e) {
			//Do nothing.
		}
	}
	
	/**
	 * @postcondition Returns a string containing the output of the traversion specified by the subtype of the tree.
	 */
	public abstract String traverse();
	
	/**
	 * Auxiliary method for search(), therefore has the same pre- and postconditions.
	 * @param label The label to look for.
	 * @param node The root of the tree to look in.
	 */
	private String suche(String label, Node node) {
		String output = "";
		
		if (node == null) {
			return "Node not found";
		}
		
		if (label.compareTo(node.toString()) == 0) {
			return "";
		}
		if (label.compareTo(node.toString()) < 0) {
			output += "left " + suche(label, node.getLeftChild()); 
		} else {
			output += "right " + suche(label, node.getRightChild());
		}
		
		if (output.contains("Node not found")) {
			return "Node not found";
		} else {
			return output;
		}
	}
	
	/**
	 * Adds a node with the given label; auxiliary method for add(), therefore it has the same pre- and postconditions.
	 * @param label The label of the node to add.
	 * @param node The root of the tree the node should be added to.
	 */
	private void recAdd(String label, Node node) {
		if (label.compareTo((String)node.toString()) < 0) {
			if (node.getLeftChild() == null) {
				node.setLeftChild(new Node(label));
			} else {
				recAdd(label, node.getLeftChild());
			}
		} else {
			if (node.getRightChild() == null) {
				node.setRightChild(new Node(label));
			} else {
				recAdd(label, node.getRightChild());
			}
		}
	}
}